# TODO: Add comment
# 
# Author: artur
###############################################################################


dominosa.createSearchGraph<-function(board) {
	chosenPoints<-list()		#lista miejsc zajętych
	chosenDominoBlocks<-list()	#lista zajętych klocków domino
	
	theGraph<-newGraph.createGraph()
	
	theGraph$addNode("0", list(list(-1, -1)), NULL ,isStartNode=TRUE)	#nothing chosen, just start point
	parentName<-"0"
	dominosa.depthFirstConstructNode(theGraph, parentName, list(list(-1, -1)), board, chosenPoints, length(board)/2+1)
	
	return(theGraph)
}


dominosa.depthFirstConstructNode<-function(theGraph, parentName, path, board, chosenPoints, parentCost) {
	theSmallestNotChosen<-dominosa.chooseTheSmallest(chosenPoints, board) #wybiera najmniejszy punkt wolny
	if(theSmallestNotChosen==FALSE)
	{
		#print("BRAK WOLNYCH PÓŁ")
		return(NULL)	
	}
	fullPathName<-list()
	#wybór punktów na planszy do domina, max dwie opcje: theSmallestNotChosen+1 i theSmallestNotChosen+m
	#gdzie m to ilość kolumn planszy
	if(theSmallestNotChosen%%ncol(board)==0 && theSmallestNotChosen%%nrow(board)==0)	#warunek, kiedy smallest na dolnym rogu
	{
		#print("JESTEM W DOLNYM ROGU")
		return(NULL)
	}
	else if(theSmallestNotChosen%%ncol(board)==0)
	{
		#co najwyżej jeden do generacji
		theSecondPoint<-theSmallestNotChosen+ncol(board)
		
		if(dominosa.isInList(chosenPoints, theSecondPoint))
		{
			#print("ZAJETE NA DOLE (jestem na prawym brzegu)")
			return(NULL)	#nie można utwożyć dominosa
		}
		newNodeName<-paste(c(theSmallestNotChosen,theSecondPoint),collapse="_")
		pathList<-path
		fullPathName<-paste(c(parentName,newNodeName), collapse="|")
		dominoBlock<-dominosa.getDominoBlock(theSmallestNotChosen, theSecondPoint, board)
		pathList[[length(pathList)+1]]<-dominosa.getDominoBlock(theSmallestNotChosen, theSecondPoint, board)
		costP<-parentCost-dominosa.cost(pathList)
		
		theGraph$addNode(paste(c(parentName,newNodeName), collapse="|"), pathList, parentName, costP, dominosa.heuristicCost(dominoBlock, board, chosenPoints) ,isEndNode=dominosa.isEndNode(costP))
		chosenPoints[[length(chosenPoints)+1]]<-theSmallestNotChosen
		chosenPoints[[length(chosenPoints)+1]]<-theSecondPoint
			
		dominosa.depthFirstConstructNode(theGraph, paste(c(parentName,newNodeName), collapse="|"), pathList, board, chosenPoints, costP)
	}
	else if(((theSmallestNotChosen%/%ncol(board))+1)%%nrow(board)==0)
	{
		theSecondPoint<-theSmallestNotChosen+1
		#co najwyżej jeden do generacji
		if(dominosa.isInList(chosenPoints, theSecondPoint))
		{
			#print("ZAJETE PO PRAWO (jestem na dole)")
			return(NULL)		#nie można utworzyć dominosy
		}
		newNodeName<-paste(c(theSmallestNotChosen,theSecondPoint),collapse="_")
		pathList<-path
		dominoBlock<-dominosa.getDominoBlock(theSmallestNotChosen, theSecondPoint, board)
		pathList[[length(pathList)+1]]<-dominosa.getDominoBlock(theSmallestNotChosen, theSecondPoint, board)
		fullPathName<-paste(c(parentName,newNodeName), collapse="|")
		costP<-parentCost-dominosa.cost(pathList)
		
		theGraph$addNode(paste(c(parentName,newNodeName), collapse="|"), pathList, parentName, costP,dominosa.heuristicCost(dominoBlock, board, chosenPoints), isEndNode=dominosa.isEndNode(costP))
		chosenPoints[[length(chosenPoints)+1]]<-theSmallestNotChosen
		chosenPoints[[length(chosenPoints)+1]]<-theSecondPoint
		
		dominosa.depthFirstConstructNode(theGraph,paste(c(parentName,newNodeName), collapse="|"),  pathList, board, chosenPoints, costP)
	}
	else
	{
		theSecondPoint<-theSmallestNotChosen+1
		#dwa do generacji, chyba że zajęte
		if(dominosa.isInList(chosenPoints, theSecondPoint))
		{
			#print("ZAJETE PO PRAWO")
		}
		else
		{
			newNodeName<-paste(c(theSmallestNotChosen,theSecondPoint),collapse="_")
			pathList<-path
			chosenP<-chosenPoints
			dominoBlock<-dominosa.getDominoBlock(theSmallestNotChosen, theSecondPoint, board)
			pathList[[length(pathList)+1]]<-dominosa.getDominoBlock(theSmallestNotChosen, theSecondPoint, board)
			fullPathName<-paste(c(parentName,newNodeName), collapse="|")
			costP<-parentCost-dominosa.cost(pathList)
			
			theGraph$addNode(paste(c(parentName,newNodeName), collapse="|"), pathList, parentName, costP, dominosa.heuristicCost(dominoBlock, board, chosenP), isEndNode=dominosa.isEndNode(costP))
			chosenP<-chosenPoints
			chosenP[[length(chosenP)+1]]<-theSmallestNotChosen
			chosenP[[length(chosenP)+1]]<-theSecondPoint
			
			dominosa.depthFirstConstructNode(theGraph, paste(c(parentName,newNodeName), collapse="|"), pathList, board, chosenP, costP)
		}
		
		
		theSecondPoint<-theSmallestNotChosen+ncol(board)
		if(dominosa.isInList(chosenPoints, theSecondPoint))
		{
			#print("ZAJETE NA DOLE")
		}
		else
		{
			newNodeName<-paste(c(theSmallestNotChosen,theSecondPoint),collapse="_")
			pathList<-path
			chosenP<-chosenPoints
			dominoBlock<-dominosa.getDominoBlock(theSmallestNotChosen, theSecondPoint, board)
			pathList[[length(pathList)+1]]<-dominosa.getDominoBlock(theSmallestNotChosen, theSecondPoint, board)
			fullPathName<-paste(c(parentName,newNodeName), collapse="|")
			costP<-parentCost-dominosa.cost(pathList)
			
			theGraph$addNode(paste(c(parentName,newNodeName), collapse="|"), pathList, parentName, costP, dominosa.heuristicCost(dominoBlock, board, chosenP), isEndNode=dominosa.isEndNode(costP))
			chosenP[[length(chosenP)+1]]<-theSmallestNotChosen
			chosenP[[length(chosenP)+1]]<-theSecondPoint
			
			dominosa.depthFirstConstructNode(theGraph, paste(c(parentName,newNodeName), collapse="|"), pathList, board, chosenP, costP)
		}
	}	
}

#Zwraca koszt heurystyczny dla metody heurystycznej
dominosa.heuristicCost<-function(dominoBlock, board, chosenPoints) {
	counter<-0	#licznik wystąpień klocka domino
	
	for(i in 1:(length(board)-length(chosenPoints))) #plus 1 bo wpisujemy 0 na poczatku
	{
		theSmallest<-dominosa.chooseTheSmallest(chosenPoints, board)
		if(theSmallest==FALSE){
			return(counter)
		}
		chosenPoints[[length(chosenPoints)+1]]<-theSmallest
		#przypadek 1
		if(theSmallest%%ncol(board)==0 && theSmallest%%nrow(board)==0)	#warunek, kiedy smallest na dolnym rogu
		{
			#print("JESTEM W DOLNYM ROGU")
		}
		else if(theSmallest%%ncol(board)==0)
		{
			#co najwyżej jeden do generacji
			if(dominosa.isInList(chosenPoints, theSmallest+ncol(board)))
			{
				#print("ZAJETE NA DOLE (jestem na prawym brzegu)")
			}	
			else
			{
				blockBoard<-dominosa.getDominoBlock(theSmallest, theSmallest+ncol(board),board)
				if((dominoBlock[[1]]==blockBoard[[1]]&&dominoBlock[[2]]==blockBoard[[2]])
						||(dominoBlock[[2]]==blockBoard[[1]]&&dominoBlock[[1]]==blockBoard[[2]]))
					counter<-counter+1
			}
		}
		else if(((theSmallest%/%ncol(board))+1)%%nrow(board)==0)
		{
			#co najwyżej jeden do generacji
			if(dominosa.isInList(chosenPoints, theSmallest+1))
			{
				#print("ZAJETE PO PRAWO (jestem na dole)")
			}
			else
			{
				blockBoard<-dominosa.getDominoBlock(theSmallest, theSmallest+1,board)
				if((dominoBlock[[1]]==blockBoard[[1]]&&dominoBlock[[2]]==blockBoard[[2]])
						||(dominoBlock[[2]]==blockBoard[[1]]&&dominoBlock[[1]]==blockBoard[[2]]))
					counter<-counter+1
			}
		}
		else
		{
			#dwa do generacji, chyba że zajęte
			if(dominosa.isInList(chosenPoints, theSmallest+1))
			{
				#print("ZAJETE PO PRAWO")
			}
			else
			{
				blockBoard<-dominosa.getDominoBlock(theSmallest, theSmallest+1,board)
				if((dominoBlock[[1]]==blockBoard[[1]]&&dominoBlock[[2]]==blockBoard[[2]])
						||(dominoBlock[[2]]==blockBoard[[1]]&&dominoBlock[[1]]==blockBoard[[2]]))
					counter<-counter+1
			}
			
			if(dominosa.isInList(chosenPoints, theSmallest+ncol(board)))
			{
				#print("ZAJETE NA DOLE")
			}
			else
			{
				blockBoard<-dominosa.getDominoBlock(theSmallest, theSmallest+ncol(board),board)
				if((dominoBlock[[1]]==blockBoard[[1]]&&dominoBlock[[2]]==blockBoard[[2]])
						||(dominoBlock[[2]]==blockBoard[[1]]&&dominoBlock[[1]]==blockBoard[[2]]))
					counter<-counter+1	
			}
		}
	}#for loop
	return(counter)
}

#Zwraca koszt przeznaczony dla funkcji heurystycznej
dominosa.cost<-function(pathList) {
	if(dominosa.uniqueLength(pathList)==-2)
		return(0)
	else
		return(1)
}

#Sprawdza czy dany element jest na liscie lisOfNumbers
dominosa.isInList<-function(listOfNumbers, element) {
	if(length(listOfNumbers)==0)
	{
		return(FALSE)
	}
	for(i in 1:length(listOfNumbers))
	{
		if(listOfNumbers[[i]]==element)
			return(TRUE)
	}
	return(FALSE)
}

#Wybiera najmniejszą pozycje na planszy, która nie jest na liscie chosenPoints
dominosa.chooseTheSmallest<-function(chosenPoints, board) {
	if(length(board)==0)
	{
		return(NULL)
	}
	for(i in 1:length(board))
	{
		if(!dominosa.isInList(chosenPoints, i))
		{
			return(i)
		}
	}
	return(FALSE)	#chosenPoints and board contaains the same elementsn
}

#Pobiera kloceke domino z planszy board na podstawie położenia na planszy(oneValue, twoValue)
dominosa.getDominoBlock<-function(oneValue, twoValue, board) {
	x1Coordinate<-(oneValue-1)%%ncol(board) + 1
	y1Coordinate<-((oneValue-1)%/%(ncol(board)))+1
	
	x2Coordinate<-(twoValue-1)%%ncol(board) + 1
	y2Coordinate<-(twoValue-1)%/%(ncol(board))+1

	x<-model.board[y1Coordinate, x1Coordinate]
	y<-model.board[y2Coordinate, x2Coordinate]
	h<-x[[1]]
	g<-y[[1]]
	
	return(list(h, g))
}

#Sprawdza czy dany węzeł jest węzłem końcowym (end node)
dominosa.isEndNode<-function(cost)
{
	if(cost==1)		#END NODE
		return(TRUE)	
	else
		return(FALSE)
}

#Zwraca wartosc -2 jeżeli lista path zawiera elementy, które się powtarzają
#jezeli są unikalne zwraca ilosc elementow w liscie
dominosa.uniqueLength<-function(path) {	#if not unique returns 1 else number of elemets
	if(length(path)==0)
		return(0)

	for(i in 1:length(path)) {
		for(j in 1:length(path)) {
			if(i!=j) {
				if((path[[i]][[1]]==path[[j]][[1]]&&path[[i]][[2]]==path[[j]][[2]])
						||(path[[i]][[1]]==path[[j]][[2]]&&path[[i]][[2]]==path[[j]][[1]]))
				{
					return(-2)
				}
			}
		}
	}
	return(length(path))
}
